Definition

For every function T:ℕ→ℕT : \mathbb{N} \to \mathbb{N} and language L⊆{0,1}∗L \subseteq \{0,1\}^*, say that L∈𝐍𝐓𝐈𝐌𝐄(T(n))L \in \mathbf{NTIME}(T(n)) if there is a constant c>0c > 0 and c⋅T(n)c \cdot T(n)-time NDTM MM such that for every x∈{0,1}∗x \in \{0,1\}^*, x∈L⟺M(x)=1x \in L \iff M(x) = 1.

In other words, 𝐍𝐓𝐈𝐌𝐄(T(n))={L|L is a language decided by an O(T(n)) NDTM}\mathbf{NTIME}(T(n)) = \{L | L \text{ is a language decided by an } O(T(n)) \text{ NDTM}\}

See also

References

  1. S. Arora, B. Barak. Computational Complexity: A Modern Approach, Cambridge University Press, 2009, p. 41.
  2. M. Sipser, Introduction to the theory of computation, Third edition, International edition. Cengage Learning, 2013, p. 295.